package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/16 9:10
 */
public class 从前序与中序遍历序列构造二叉树105 {
    Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //前序遍历的第一个值为根节点值,中序遍历将节点分为左右
        return recur(preorder, inorder);
    }

    public TreeNode recur(int[] pre, int[] in) {
        if (pre.length == 0 && in.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        int i = map.get(pre[0]);
        //找到中间值 1,2,3,4,5
        int[] preLeft = Arrays.copyOfRange(pre, 1, i + 1);
        int[] preRight = Arrays.copyOfRange(pre, i + 1, pre.length);
        int[] inLeft = Arrays.copyOfRange(in, 0, i);
        int[] inRight = Arrays.copyOfRange(in, i + 1, pre.length);
        node.left = buildTree(preLeft, inLeft);
        node.right = buildTree(preRight, inRight);
        return node;
    }
}
